package algorithm;

public class leetcode_0188 {
    public int maxProfit(int k, int[] prices) {
        int len=prices.length;
        if(len==0) return 0;
        int[][] dp=new int[len][2*k];
        for(int i=0;i<2*k;++i){
            if(i%2==0) dp[0][i]=-1*prices[0];
            else dp[0][i]=0;
        }
        for(int i=1;i<len;++i){
            for(int l=0;l<2*k;++l){
                if(l==0) dp[i][l]=max(dp[i-1][l],-1*prices[i]);
                else if(l%2==0) dp[i][l]=max(dp[i-1][l],dp[i-1][l-1]-1*prices[i]);
                else dp[i][l]=max(dp[i-1][l],dp[i-1][l-1]+prices[i]);
            }
        }
        int max=0;
        for(int i=1;i<2*k;i+=2){
            max=(max>dp[len-1][i])?max:dp[len-1][i];
        }
        return max;
    }
    public int max(int a,int b){
        return (a<b)?b:a;
    }
}
